#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cassert>

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include "IteratorRange.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<int>::iterator global_iterator;

struct Operation
{
	int value, type;
	Operation() : value(0), type(0) {}
	Operation(const int value, const int type) : value(value), type(type) {}
};

template <class Sequence>
bool checkDiagonalPushArray(const Sequence &left_data_sequence, const Sequence &right_data_sequence, const int distance, const vector<int> &expected_value);

template <class Sequence>
int getLongestCommonPrefix(const Sequence &A, const Sequence &B)
{
	auto it = A.begin();
	auto jt = B.begin();
	while (it != A.end() && jt != B.end())
		if ((*it) != (*jt)) return it - A.begin();
		else it++, jt++;
	return it - A.begin();
}

template <class Iterator>
pair<vector<int>, int> getDiagonalPushArray(const IteratorRange<Iterator> &left_data_sequence, const IteratorRange<Iterator> &right_data_sequence, const int distance = -1)
{
	int len_left = left_data_sequence.size(), len_right = right_data_sequence.size(); int answer = -1;
	vector<int> result(2 * (len_left + len_right) + 1);
	int shift = len_left + len_right; result[shift] = 2 * getLongestCommonPrefix(left_data_sequence, right_data_sequence);
	for (int d = 0; d < (distance == -1 ? len_right + len_left + 1: distance); d++)
	{
		if (result[len_right - len_left + shift] == len_right + len_left)
		{
			answer = d;
			break;
		}
		for (int k = -d; k <= d; k += 2)
		{
			int x = (result[k + shift] - k) >> 1, y = (result[k + shift] + k) >> 1;
			if (x < 0 || x > len_left || y < 0 || y > len_right) continue;
			if (x < len_left)
			{
				int upd = getLongestCommonPrefix(left_data_sequence.Shrink(x + 1, 0), right_data_sequence.Shrink(y, 0));
				result[k - 1 + shift] = max(result[k - 1 + shift], x + 1 + y + 2 * upd);
			}
			else if (y > 0) result[k - 1 + shift] = x + y - 1;
			if (y < len_right)
			{
				int upd = getLongestCommonPrefix(left_data_sequence.Shrink(x, 0), right_data_sequence.Shrink(y + 1, 0));
				result[k + 1 + shift] = max(result[k + 1 + shift], x + y + 1 + 2 * upd);
			}
			else if (x > 0) result[k + 1 + shift] = x + y - 1;
		}
	}
	if (distance == -1) assert(result[len_right - len_left + shift] == len_right + len_left);
	return make_pair(result, answer);
}

template <class Sequence>
vector<Operation> getOperationSequence(const Sequence &data_sequence, const int operation_type)
{
	vector<Operation> result;
	for (auto it = data_sequence.begin(); it != data_sequence.end(); it++)
		result.push_back(Operation((*it), operation_type));
	return result;
}

template <class Sequence>
vector<Operation> getModifiedOperationSequence(const Sequence &left_data_sequence, const Sequence &right_data_sequence)
{
	vector<Operation> result;
	assert(left_data_sequence.size() == right_data_sequence.size() + 1 || left_data_sequence.size() + 1 == right_data_sequence.size());
	auto ptr1 = left_data_sequence.begin(), ptr2 = right_data_sequence.begin();
	while (ptr1 != left_data_sequence.end() && ptr2 != right_data_sequence.end())
		if ((*ptr1) == (*ptr2)) result.push_back(Operation(*(ptr1), 0)), ptr1++, ptr2++;
		else if (left_data_sequence.size() == right_data_sequence.size() + 1) result.push_back(Operation(*(ptr1), -1)), ptr1++;
		else result.push_back(Operation(*(ptr2), 1)), ptr2++;
	if (ptr1 != left_data_sequence.end()) result.push_back(Operation(*(ptr1), -1));
	if (ptr2 != right_data_sequence.end()) result.push_back(Operation(*(ptr2), 1));
	return result;
}

template <class Iterator>
vector<Operation> getCorrectionSequence(const IteratorRange<Iterator> &left_data_sequence, const IteratorRange<Iterator> &right_data_sequence, const int distance)
{
	int len_left = left_data_sequence.size(), len_right = right_data_sequence.size();
	if (distance == len_left + len_right)
	{
		vector<Operation> resA = getOperationSequence(left_data_sequence, -1), resB = getOperationSequence(right_data_sequence, 1);
		for (size_t i = 0; i < resB.size(); i++)
			resA.push_back(resB[i]);
		return resA;
	}
	if (distance == 1) return getModifiedOperationSequence(left_data_sequence, right_data_sequence);
	if (distance == 0) return getOperationSequence(left_data_sequence, 0);
	vector<int> left = getDiagonalPushArray(left_data_sequence, right_data_sequence, (distance + 1) / 2).first,
				right = getDiagonalPushArray(left_data_sequence.Reversed(), right_data_sequence.Reversed(), distance / 2).first;
	int dx_left = -1, dy_left = -1, shift = len_left + len_right;
	for (int i = -distance; i <= distance; i++)
	{
		int j = len_right - len_left - i;
		if (j < -distance || j > distance) continue;
		int delta_expected = (i < 0 ? min(len_left + i, len_right) : min(len_left, len_right - i)),
			delta_left = (left[i + shift] - abs(i)) / 2,
			delta_right = (right[j + shift] - abs(j)) / 2;
		if (delta_left + delta_right >= delta_expected)
		{
			dx_left = dy_left = delta_left;
			if (i < 0) dx_left -= i;
			else dy_left += i;
		}
	}
	IteratorRange<Iterator> tmp_left = left_data_sequence.Shrink(0, len_left - dx_left),
		tmp_right = right_data_sequence.Shrink(0, len_right - dy_left);
	vector<Operation> result = getCorrectionSequence(tmp_left, tmp_right, (distance + 1) / 2);
	tmp_left = tmp_left.Shrink(dx_left, dx_left - len_left), tmp_right = tmp_right.Shrink(dy_left, dy_left - len_right);
	vector<Operation> add_result = getCorrectionSequence(tmp_left, tmp_right, distance / 2);
	for (uint i = 0; i < add_result.size(); i++)
		result.push_back(add_result[i]);
	return result;
}

template <class Sequence>
bool checkCorrectionSequence(const vector<Operation> &result, const Sequence &left_data_sequence, const Sequence &right_data_sequence)
{
	auto it = left_data_sequence.begin(), jt = right_data_sequence.begin();
	for (size_t i = 0; i < result.size(); i++)
	{
		if (result[i].type == 1)
		{
			if (jt != right_data_sequence.end() && (*jt) == result[i].value) jt++;
			else { cerr << "Wrong action " << result[i].type << ' ' << result[i].value << " at position " << i << endl; return false; }
		}
		else if (result[i].type == -1)
		{
			if (it != left_data_sequence.end() && (*it) == result[i].value) it++;
			else { cerr << "Wrong action " << result[i].type << ' ' << result[i].value << " at position " << i << endl; return false; }
		}
		else
		{
			if (it != left_data_sequence.end() && (*it) == result[i].value && jt != right_data_sequence.end() && (*jt) == result[i].value) it++, jt++;
			else { cerr << "Wrong action " << result[i].type << ' ' << result[i].value << " at position " << i << endl; return false; }
		}
	}
	return true;
}

template <class Sequence>
vector<vector<int> > getEditDistanceMatrix(const Sequence &left_data_sequence, const Sequence &right_data_sequence)
{
	int len_left = left_data_sequence.size(), len_right = right_data_sequence.size();
	vector<vector<int> > edit_distance_matrix(len_left + 1);
	for (int i = 0; i <= len_left; i++)
		edit_distance_matrix[i].resize(len_right + 1, len_left + len_right);
	edit_distance_matrix[0][0] = 0;
	auto it = left_data_sequence.begin(), jt = right_data_sequence.begin();
	for (int i = 0; i <= len_left; i++)
	{
		jt = right_data_sequence.begin();
		for (int j = 0; j <= len_right; j++)
		{
			if (edit_distance_matrix[i][j] == len_left + len_right) continue;
			if (i < len_left) edit_distance_matrix[i + 1][j] = min(edit_distance_matrix[i + 1][j], edit_distance_matrix[i][j] + 1);
			if (j < len_right) edit_distance_matrix[i][j + 1] = min(edit_distance_matrix[i][j + 1], edit_distance_matrix[i][j] + 1);
			if (i < len_left && j < len_right && (*it) == (*jt)) edit_distance_matrix[i + 1][j + 1] = min(edit_distance_matrix[i + 1][j + 1], edit_distance_matrix[i][j]);
			if (j != len_right) jt++;
		}
		if (i != len_left) it++;
	}
	return edit_distance_matrix;
}

template <class Sequence>
bool checkDiagonalPushArray(const Sequence &left_data_sequence, const Sequence &right_data_sequence, const int distance, const vector<int> &expected_value)
{
	vector<vector<int> > edit_distance_matrix = getEditDistanceMatrix(left_data_sequence, right_data_sequence);
	int len_left = left_data_sequence.size(), len_right = right_data_sequence.size();
	vector<int> result(2 * (len_left + len_right) + 1, 0); int shift = len_left + len_right;
	for (int i = 0; i <= len_left; i++)
		for (int j = 0; j <= len_right; j++)
			if (edit_distance_matrix[i][j] <= distance) result[shift + j - i] = max(result[shift + j - i], i + j);
	bool failure = false;
	for (int i = shift - distance; i <= shift + distance; i++)
		if (result[i] != expected_value[i])
		{
			cerr << "Wrong value on diagonal with number " << i << endl;
			failure = true;
		}
	return !failure;
}

template <class Sequence>
bool checkCorrectionSequenceLength(const Sequence &left_data_sequence, const Sequence &right_data_sequence, const int expected_value)
{
	int n = left_data_sequence.size(), m = right_data_sequence.size();
	vector<vector<int> > edit_distance_matrix = getEditDistanceMatrix(left_data_sequence, right_data_sequence);
	if (edit_distance_matrix[n][m] != expected_value)
		cerr << "Wrong correction sequence length : " << expected_value << " instead of " << edit_distance_matrix[n][m] << endl;
	return (edit_distance_matrix[n][m] == expected_value);
}

template <class Sequence>
bool checkLongestCommonPrefix(const Sequence &A, const Sequence &B, bool suff_array, const int expected_value)
{
	// if suffix array is used -- check with simple algo;
	// if suffix array is not used -- check with some prewritten tests;
	int length = getLongestCommonPrefix(A, B);
	if (length != expected_value)
		cerr << "Wrong length of common prefix : " << expected_value << " instead of " << length << endl;
	return (length == expected_value);
}

// check with prewritten tests (suffix array is not used);
void testLongestCommonPrefix()
{
	const int number_of_tests = 5;
	string left_data[number_of_tests] = { "abcdasd", "efsdg", "aaaaf", "abababababababababababababababa", "xzy" };
	string right_data[number_of_tests] = { "abcd", "efsdgaaw", "aaaaf", "ababababababababababaababababab", "xyz" };
	int expected_value[number_of_tests] = { 4, 5, 5, 21, 1 };
	for (int i = 0; i < number_of_tests; i++)
	{
		if (!checkLongestCommonPrefix(left_data[i], right_data[i], false, expected_value[i]))
			cerr << "Failure on " << left_data[i] << ' ' << right_data[i] << endl;
	}
}

vector<int> generateRandomSequence(const int max_length, const int max_value)
{
	int length = rand() % max_length + 1;
	vector<int> result(length);
	for (int i = 0; i < length; i++)
		result[i] = rand() % max_value;
	return result;
}

void testDiagonalPushArray()
{
	int tests = 100;
	vector<int> first_sequence, second_sequence;
	pair<vector<int>, int> result;
	for (int i = 0; i < tests; i++)
	{
		first_sequence = generateRandomSequence(1000, 100),
		second_sequence = generateRandomSequence(1000, 100);
		IteratorRange<global_iterator> RangeA(first_sequence.begin(), first_sequence.end()),
			RangeB(second_sequence.begin(), second_sequence.end());
		result = getDiagonalPushArray(RangeA, RangeB);
		if (!checkDiagonalPushArray(RangeA, RangeB, result.second, result.first))
			cerr << "Wrong behavior on test " << i + 1 << endl;
	}
}

// for sequences built with getCorrectionSequence()
// (means that A and B are sequences of ints because of structure of "Operation");
void testCorrectionSequence()
{
	int tests = 100;
	vector<int> first_sequence, second_sequence;
	for (int i = 0; i < tests; i++)
	{
		first_sequence = generateRandomSequence(1000, 100),
			second_sequence = generateRandomSequence(1000, 100);
		IteratorRange<global_iterator> RangeA(first_sequence.begin(), first_sequence.end()),
			RangeB(second_sequence.begin(), second_sequence.end());
		int distance = getDiagonalPushArray(RangeA, RangeB).second;
		vector<Operation> result = getCorrectionSequence(RangeA, RangeB, distance);
		int changes = 0;
		for (size_t j = 0; j < result.size(); j++)
			if (result[j].type != 0) changes++;
		if (!checkCorrectionSequenceLength(RangeA, RangeB, changes) ||
			!checkCorrectionSequence(result, RangeA, RangeB))
			cerr << "Wrong behavior on test " << i + 1 << endl;
	}
}

vector<string> readFile(const string &filename)
{
	string s; vector<string> result;
	ifstream input(filename);
	while (getline(input, s))
		result.push_back(s);
	input.close();
	return result;
}

vector<int> digitize(const vector<string> &strings, map<string, int> &string_ids)
{
	int size = string_ids.size();
	vector<int> result;
	for (size_t i = 0; i < strings.size(); i++)
	{
		pair<map<string, int>::iterator, bool> v = string_ids.insert(make_pair(strings[i], size));
		if (v.second) size++;
		result.push_back(v.first->second);
	}
	return result;
}

string generateRandomString(const int max_length)
{
	string s; int length = rand() % max_length;
	for (int i = 0; i < length; i++)
		s.push_back((rand() & 1) ? 'a' : 'b');
	return s;
}

vector<string> generateRandomStrings(const int max_size, const int max_length)
{
	int length = rand() % max_size + 1;
	vector<string> result(length);
	for (int i = 0; i < length; i++)
		result[i] = generateRandomString(max_length);
	return result;
}

void testStringDigitizing()
{
	int tests = 100;
	vector<string> first_strings, second_strings;
	map<string, int> string_ids;
	vector<int> first_sequence, second_sequence;
	for (int i = 0; i < tests; i++)
	{
		first_strings = generateRandomStrings(1000, 10);
		second_strings = generateRandomStrings(1000, 10);
		string_ids.clear();
		first_sequence = digitize(first_strings, string_ids);
		second_sequence = digitize(second_strings, string_ids);
		bool good = true;
		for (size_t i = 0; i < first_sequence.size() && good; i++)
			for (size_t j = 0; j < second_sequence.size() && good; j++)
				if ((first_sequence[i] == second_sequence[j]) ^ (first_strings[i] == second_strings[j]))
				{
					good = false;
					cerr << "Wrong behavior on test " << i + 1 << endl;
					cerr << first_strings[i] << ' ' << first_sequence[i] << ' ' << second_sequence[j] << ' ' << second_strings[j] << endl;
				}
	}
}

template <class Iterator>
void findDifference(const IteratorRange<Iterator> &first_sequence, const IteratorRange<Iterator> &second_sequence, const vector<string> &reverse_ids)
{
	int distance = getDiagonalPushArray<Iterator>(first_sequence, second_sequence).second;
	vector<Operation> result = getCorrectionSequence<Iterator>(first_sequence, second_sequence, distance);
	for (size_t i = 0; i < result.size(); i++)
	{
		char c = ' ';
		if (result[i].type == -1) c = '-';
		if (result[i].type == 1) c = '+';
		cout << c << ' ' << reverse_ids[result[i].value] << endl;
	}
}

void exitWithUsageError()
{
	cerr << "USAGE: -t // to launch testing sequence.\n";
	cerr << "USAGE: <file_1> <file_2> // to find difference in lines." << endl;
	exit(0);
}

int main(int argc, char** argv)
{
	if (argc == 2)
	{
		if (strcmp(argv[1], "-t") != 0)
			exitWithUsageError();
		srand(12345679);
		cerr << "Testing \"Longest Common Prefix\" unit.\n";
		testLongestCommonPrefix();
		cerr << "Testing \"Diagonal Push\" unit.\n";
		testDiagonalPushArray();
		cerr << "Testing \"String Digitizing\" unit.\n";
		testStringDigitizing();
		cerr << "Testing \"Correction Sequence\" unit.\n";
		testCorrectionSequence();
		return 0;
	}
	if (argc != 3)
		exitWithUsageError();

	map<string, int> string_ids;
	vector<string> reverse_ids;
	vector<string> first_strings = readFile(argv[1]),
		second_strings = readFile(argv[2]);
	vector<int> first_sequence = digitize(first_strings, string_ids),
		second_sequence = digitize(second_strings, string_ids);
	reverse_ids.resize(string_ids.size());
	for (map<string, int>::iterator it = string_ids.begin(); it != string_ids.end(); it++)
		reverse_ids[it->second] = it->first;

	IteratorRange<global_iterator> RangeA(first_sequence.begin(), first_sequence.end()),
		RangeB(second_sequence.begin(), second_sequence.end());
	findDifference<global_iterator>(RangeA, RangeB, reverse_ids);
	return 0;
}